Back Lowest common ancestor English Ancestro común más bajo Spanish پایین‌ترین جد مشترک Persian Plus petit ancêtre commun French Najniższy wspólny przodek Polish Наименьший общий предок Russian Найменший спільний предок Ukrainian 最近公共祖先 (图论) Chinese

Lowest Common Ancestor

In diesem Baum ist der LCA der Knoten x und y in Dunkelgrün mar­kiert. Andere ge­mein­same Vorfahren sind in Hellgrün dar­ge­stellt.

Als Lowest Common Ancestor oder Least Common Ancestor (LCA), deutsch „letzter gemeinsamer Vorfahre“, wird in der Informatik und Graphentheorie ein Ermittlungskonzept bezeichnet, das einen gegebenen gewurzelten Baum von Datenstrukturen effizient vor­ver­arbei­tet, sodass anschließend Anfragen nach dem letzten gemeinsamen Vorfahren für beliebige Knotenpaare in konstanter Zeit beantwortet werden können.

Bäume gehören zu den fundamentalen Datenstrukturen der Informatik. Sie werden häufig verwendet, um Daten in einer hierarchischen oder geschachtelten Struktur darzustellen. Zwei klassische Beispiele sind Such- und Entscheidungsbäume. Algorithmische Standard­fragen für Bäume sind zum Beispiel die Pre-, Post- und Inordertraversierung. Ein in diesem Kontext weniger bekanntes algorithmisches Problem ist die Suche nach dem letzten ge­mein­samen Vorfahren (LCA).[1]

  1. ↑ Effiziente Berechnung vom letzten ge­mein­samen Vorfahren und Anwendungen – FU Berlin. Auf: fu-berlin.de – abgerufen am 22. Januar 2023

Developed by StudentB